package SubjectBacktracking.One;

import java.util.ArrayList;
import java.util.List;

public class CombinationSum3 {

/**
 * 难度：中等
 * 
 * 216. 组合总和 III
 * 	找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
 * 	
 * 说明：
 * 	所有数字都是正整数。
 * 	解集不能包含重复的组合。 
 * 	
 * 示例 1:
 * 	输入: k = 3, n = 7
 * 	输出: [[1,2,4]]
 * 	
 * 示例 2:
 * 	输入: k = 3, n = 9
 * 	输出: [[1,2,6], [1,3,5], [2,3,4]]
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		CombinationSum3 cs3 = new CombinationSum3();
		System.out.println(cs3.combinationSum3(9, 45));
	}
	//自己写
	List<List<Integer>> result = new ArrayList<>();
	List<Integer> path = new ArrayList<>();
	public List<List<Integer>> combinationSum3(int k, int n) {
		backtracking(k,n,1);
		return result;
    }
	private void backtracking(int k,int n,int startIndex) {
		if(path.size() == k && n==0) {
			result.add(new ArrayList<>(path));
			return;
		}else if(n<0) {
			return;
		}
		for(int i=startIndex;i<=9;i++) {
			path.add(i);
			backtracking(k,n-i,i+1);
			path.remove(path.size()-1);
		}
	}
}
